package com.algorithm.learning.base.图;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/29 21:24
 **/
public class 图的宽度优先遍历 {

    /**
     *
     * 宽度优先遍历：如果需要寻找最短路径，BFS通常是更好的选择
     *
     * 1、访问顺序：从起始节点开始，先访问所有与起始节点直接相连的节点，然后再访问这些节点的邻居节点，以此类推，逐层向外扩展。
     * 2、通常用Queue实现
     * 3、应用场景：适合于寻找两个节点之间的最短路径（在无权图中）、验证图是否是二分图、计算所有节点到一个固定节点的最短距离等问题。
     * 4、特点：保证了从一个节点出发到另一个节点的最短路径（在无权图中）。
     *
     *
     * 就是给你一个节点，先找到离我最近的一层，然后再找到离我第二层的节点，依次类推，直到遍历完所有的节点。
     *     a ↔ b
     *    ↙ ↘      ↖
     *   c → d → e → f
     *
     * 对于上的一个图，假如传入的节点是a，
     * 那么对于a来说, 他直接连接的点就是第一层的节点，也就是b、c、d, 而这一层的节点遍历是不分顺序的。
     *
     * 而 e 表示第二层，f表示第三层，
     *
     * 所以打印的结果就是: a → b → c → d → e → f, 其中要注意：b、c、d的顺序可以变
     *
     * @param node
     */
    public static void bfs(Node node) {
        if (node == null) {
            return;
        }

        // 创建一个队列，用于存储待遍历的节点
        Queue<Node> queue = new LinkedList<>();
        // 创建一个集合，用于存储已经遍历过的节点
        Set<Node> set = new HashSet<>();
        // 将传入的节点加入队列
        queue.add(node);
        set.add(node);

        while (!queue.isEmpty()) {
            // 从队列中取出一个节点
            Node cur = queue.poll();
            System.out.println(cur.value);
            // 这里直接遍历当前点的直接邻居
            for (Node next : node.nexts) {
                // 如果弹出的节点不在set中，就不需要重复处理
                // 这里就需要Set集合来避免重复处理同一个点。
                /*
                      a ↔ b
                     ↙ ↖      ↖
                    c → d → e → f
                    1、对于上面的图来说，假如传入的点是a，那么a的nexts就是 b,c,d
                    2、此时b,c,d都不在set中，所以b、c、d都可以进队列(不保证顺序)
                    3、假如是c点先入队，那么在遍历c的nexts那就是d，此时d不在set中，所以d入队。
                    4、此时遍历d的nexts[a, e], 到这里就可以看到，d的nexts点又包含了a，而a已经放到set集合中，所以不会在入队，而是继续遍历，直到把e点入队
                 */
                if (!set.contains(next)) {
                    queue.add(next);
                    set.add(next);
                }
            }
        }
    }
}
